package com.zhugang.week12;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: findAnagrams
 * @author: chanzhugang
 * @create: 2022/09/07 22:50
 */
public class FindAngrams {

    /**
     * 438 找到字符串中所有字母异位词
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAngrams(String s, String p) {
        // s中找p的异位词子串，返回子串起始索引
        // 有点复杂，没想明白

        int n = s.length();
        int m = p.length();
        if (m > n) {
            return new ArrayList<>();
        }
        int[] needs = new int[26];
        for (int i = 0; i < m; i++) {
            // 构建一一映射的数组： 数组值是字符出现的次数
            needs[p.charAt(i) - 'a']++;
        }

        int[] matched = new int[26];

        int startp = 0;
        int endp = 0;
        List<Integer> result = new ArrayList<>();
        while (endp < m) {
            // 字符转数字
            matched[s.charAt(endp) - 'a']++;
            endp++;
        }
        if (same(needs, matched)) {
            result.add(startp);
        }

        while (endp < n && startp < n) {
            matched[s.charAt(startp) - 'a']--;
            matched[s.charAt(endp) - 'a']++;
            startp++;
            endp++;
            if (same(needs, matched)) {
                result.add(startp);
            }
        }
        return result;
    }

    private boolean same(int[] needs, int[] matched) {
        for (int i = 0; i < needs.length; i++) {
            if (needs[i] != matched[i]) {
                return false;
            }
        }
        return true;
    }
}